package hot100;

import java.util.HashMap;
import java.util.Map;

public class Solution437 {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        int ans = dfs(root, targetSum);
        ans += pathSum(root.left, targetSum);
        ans += pathSum(root.right, targetSum);
        return ans;
    }

    public int dfs(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        int path = 0;
        if (sum == root.val) {
            path++;
        }
        path += dfs(root.left, sum - root.val);
        path += dfs(root.right, sum - root.val);
        return path;
    }

    // 前缀和
    public int pathSum1(TreeNode root, int targetSum) {
        Map<Integer, Integer> prefix = new HashMap<>();
        prefix.put(0, 1);
        return prefixSum(root, prefix, 0, targetSum);
    }

    public int prefixSum(TreeNode root, Map<Integer, Integer> prefix, int sum, int target) {
        if (root == null) {
            return 0;
        }
        sum += root.val;
        // 历史路径中是否存在前缀和为sum - target的路径数
        int path = prefix.getOrDefault(sum - target, 0);
        prefix.put(sum, prefix.getOrDefault(sum, 0) + 1);
        path += prefixSum(root.left, prefix, sum, target);
        path += prefixSum(root.right, prefix, sum, target);
        prefix.put(sum, prefix.getOrDefault(sum, 0) - 1);
        return path;
    }
}
